import java.util.ArrayDeque;

public class Solution739 {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] ans = new int[n];
        //栈用于存储数组的index
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        /**
         *  1.递减栈，下面大 上面小,栈里面存数组的下标
         *
         */
        for (int i = n - 1; i >= 0; i--) {
            //保证是递减栈
            while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
                stack.pop();
            }
            //如果全部弹出去
            if (stack.isEmpty()) {
                ans[i] = 0;
            } else {
                ans[i] = stack.peek() - i;
            }
            //比较、计算后，才压入栈
            stack.push(i);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] t = {73,74,75,71,69,72,76,73};
        int[] ints = new Solution739().dailyTemperatures(t);
        System.out.println(ints);

        for (int i :
                ints) {
            System.out.println(i);
        }
    }
}
